The present invention relates to the field of data storage, and particularly to error correcting systems and methods employing on-the-fly algebraic error correcting codes. More specifically, this invention relates to an improved method for transforming an error locator polynomial into two polynomials whose roots are elements in a smaller subfield, in order to significantly simplify the complexity of the error location calculation implementation.
The use of cyclic error correcting codes in connection with the storage of data in storage devices is well established and is generally recognized as a reliability requirement for the storage system. Generally, the error correcting process involves the processing of syndrome bytes to determine the location and value of each error. Non-zero syndrome bytes result from the exclusive-ORing of error characters that are generated when data is written on the storage medium.
The number of ECC check characters employed depends on the desired power of the code. As an example, in many present day ECC systems used in connection with the storage of 8-bit bytes in a storage device, two check bytes are used for each error to be corrected in a codeword having a length of at most 255 byte positions. Thus, for example, six check bytes are required to correct up to three errors in a block of data having 249 data bytes and six check bytes. Six distinctive syndrome bytes are therefore generated in such a system. If there are no errors in the data word comprising the 255 bytes read from storage, then the six syndrome bytes contain an all zero pattern. Under such a condition, no syndrome processing is required and the data word may be sent to the central processing unit. However, if one or more of the syndrome bytes are non-zero, then syndrome processing involves the process of identifying the location of the bytes in error and further identifying the error pattern for each error location.
The underlying mathematical concepts and operations involved in normal syndrome processing operations have been described in various publications. These operations and mathematical explanations generally involve first identifying the location of the errors by use of what has been referred to as the xe2x80x9cerror locator polynomialxe2x80x9d. The overall objective of the mathematics involved employing the error locator polynomial is to define the locations of the bytes in error by using only the syndrome bytes that are generated in the system.
The error locator polynomial has been conventionally employed as the start of the mathematical analysis to express error locations in terms of syndromes, so that binary logic may be employed to decode the syndrome bytes into first identifying the locations in error, in order to enable the associated hardware to identify the error patterns in each location.
Moreover, error locations in an on-the-fly ECC used in storage or communication systems are calculated as roots of the error locator polynomial. The calculation of the roots represents a bottleneck in the implementation of the on-the-fly ECC. In certain designs, the roots calculation is done by explicit formulas whose hardware implementation becomes increasingly complex as the number of correctable errors increases.
In other designs, the roots calculation is done by an iterative search over all possible data symbol locations. The latency of these designs can be excessive, which requires several searches to be conducted in parallel over disjoint phases of symbol locations, and to be implemented in the arithmetic of the finite field that covers the complete data set.
Thus, there is still an unsatisfied need for a method that reduces the problem of searching over a large sector to searches over a smaller finite subfield for reducing the complexity and resulting latency of the hardware implementation.
In accordance with the present invention, a method is provided to transform an error locator polynomial into two new polynomials whose roots are elements in a smaller subfield, in order to significantly simplify the complexity, and to reduce the latency of the error correcting system hardware implementation.
The above and other features of the present invention are realized by an on-the-fly algebraic error correction system and corresponding method for reducing error location search. The method transforms an error locator polynomial into two transformed polynomials whose roots are elements in a smaller subfield, in order to significantly simplify the complexity, and to reduce the latency of the error correcting system hardware implementation.
More specifically, if the error locator polynomial is over a finite field of (22n) elements, the transformed polynomials are over a finite subfield of (2n) elements. Thus, the problem of locating the roots of the error locator polynomial is reduced to locating the roots of the transformed polynomials. Assuming the error locator polynomial is of degree m, the present method requires at most (m2/2) evaluations of polynomials over the Galois field GF(22n), along with root finding of two polynomials of degree m over the Galois subfield GF(2n).